// https://www.lintcode.com/problem/matching-of-parentheses/

public class Solution {
    /**
     * @param string: A string
     * @return: whether the string is a valid parentheses
     */
    public boolean matchParentheses(String string) {
        // write your code here
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < string.length(); ++i) {
            Character c = string.charAt(i);
            if (c == '(') {
                s.push(c);
            } else {
                if ((!s.empty()) && (s.peek() == '(')) {
                    s.pop();
                } else {
                    return false;
                }
            }
        }
        return s.empty();
    }
}